/**
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 *
 *https://leetcode.cn/problems/recover-binary-search-tree/
 * 思路：Morris中序遍历
 */
class RecoverTreeMorris {
    public void recoverTree(TreeNode root) {
        TreeNode  predecessor=null;
        TreeNode pre=null;
        TreeNode x=null,y=null;
        while(root!=null){
            if(root.left!=null){
                predecessor=root.left;
                while(predecessor.right!=null&&predecessor.right!=root){
                    predecessor=predecessor.right;
                }
                if(predecessor.right==null){
                    predecessor.right=root;
                    root=root.left;
                }else{
                    if(pre!=null&&pre.val>root.val){
                        y=root;
                        if(x==null){
                            x=pre;
                        }
                    }
                    pre=root;
                    predecessor.right=null;
                    root=root.right;
                }
            }else{
                if(pre!=null&&pre.val>root.val){
                        y=root;
                        if(x==null){
                            x=pre;
                        }
                    }
                    pre=root;
                root=root.right;
            }
        }
        swap(x,y);
    }
    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }


}